
\subsection{堆}

堆是一种数据结构，维护一个数的集合（或者，一个支持比较的元素的集合）。

主要功能有：insert, getmin, deletemin, decreasekey。

注意：简单起见，我们这里讨论的都是维护最小值的堆，也叫小根堆，与之相对的叫做大根堆。

一些功能强大的堆还能（高效地）支持 merge 等操作。

一些功能更强大的堆还支持可持久化，也就是对任意历史版本进行查询或者操作，产生新的版本。

\subsection{堆的分类}

一个有趣的事实是，这些堆都是用基于树的数据结构实现的。

在 NOIP 中，我们只要求一个能支持主要操作的堆就行，也就是二叉堆。

\begin{itemize}
\item 二叉堆 {\em (binary heap) }
\end{itemize}

最基础的堆，不支持 merge 和可持久化，所有操作的复杂度都是 $O(\log n)$ 的。

\begin{itemize}
\item 二项堆 {\em (binomial heap) }
\end{itemize}

支持 merge 的堆，（也能可持久化），所有操作的复杂度都是 $O(\log n)$。

\begin{itemize}
\item Fib 堆 {\em (Fibonacci heap) }
\end{itemize}

除了不能可持久化，支持全部功能，而且除了 deletemin 以外都是均摊 $O(1)$ 的。

\subsection{二叉堆}

\subsubsection{结构}

从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。

堆性质：父亲的权值不大于儿子的权值 （小根堆）。

由堆性质，树根存的是最小值 （getmin 操作就解决了）。

\subsubsection{插入操作}

首先，要保证插入后也是一棵完全二叉树。

最简单的方法就是，最下一层最右边的叶子之后插入。

如果最下一层已满，就新增一层。

插入之后可能会不满足堆性质？

向上调整：如果这个结点的权值大于它父亲的权值，就交换，重复此过程直到不满足或者到根。

可以证明，插入之后向上调整后，没有其他结点会不满足堆性质。

向上调整的时间复杂度是 $O(\log n)$ 的。

\subsubsection{删除操作}

删除根结点。

如果直接删除，则变成了两个堆，难以处理。

所以不妨考虑插入操作的逆过程，设法将根结点移到最后一个结点，然后直接删掉。

然而实际上不好做，我们通常采用的方法是，把根结点和最后一个结点直接交换。

于是直接删掉（在最后一个结点处的）根结点，但是新的根结点可能不满足堆性质……

向下调整：在该结点的所有儿子中，找一个最小的，与该结点交换，重复此过程直到底层。

可以证明，删除并向下调整后，没有其他结点不满足堆性质。

时间复杂度 $O(\log n)$。

\subsubsection{减小某个点的权值}

很显然，直接修改后，向上调整一次即可，时间复杂度为 $O(\log n)$。

\subsubsection{实现}

我们发现，上面介绍的几种操作主要依赖于两个核心：向上调整和向下调整。

（伪代码）

\begin{cppcode}
up(x) {
  while (x > 1 && h[x] > h[x / 2]) {
    swap(h[x], h[x / 2]);
    x /= 2;
  }
}
down(x) {
  while (x * 2 <= n) {
    t = x * 2;
    if (t + 1 <= n && h[t + 1] < h[t]) t++;
    if (h[t] >= h[x]) break;
    swap(h[x], h[t]);
    x = t;
  }
}
\end{cppcode}

\subsubsection{建堆}

考虑这么一个问题，从一个空的堆开始，插入 $n$ 个元素，不在乎顺序。

直接一个一个插入需要 $O(n \log n)$ 的时间，有没有更好的方法？

\paragraph{方法一：使用 decreasekey（即，向上调整）}

从根开始，按 BFS 序进行.

\begin{minted}{text}
build_heap_1() {
  for (i = 1; i <= n; i++) up(i);
}
\end{minted}

为啥这么做：对于第 $k$ 层的结点，向上调整的复杂度为 $O(k)$ 而不是 $O(\log n)$。

总复杂度：$\log 1 + \log 2 + \cdots + \log n = \Theta(n \log n)$。

（在「基于比较的排序」中证明过）

\paragraph{方法二：使用向下调整}

这时换一种思路，从叶子开始，逐个向下调整

\begin{minted}{text}
build_heap_2() {
  for (i = n; i >= 1; i--) down(i);
}
\end{minted}

换一种理解方法，每次「合并」两个已经调整好的堆，这说明了正确性。

注意到向下调整的复杂度，为 $O(\log n - k)$。

$$
\begin{aligned}
总复杂度 & = n \log n - \log 1 - \log 2 - \cdots - \log n \\\\
& \leq n \log n - 0 \times 2^0 - 1 \times 2^1 -\cdots - (\log n - 1) \times \frac{n}{2} \\\\
& = n \log n - (n-1) - (n-2) - (n-4) - \cdots - (n-\frac{n}{2}) \\\\
& = n \log n - n \log n + 1 + 2 + 4 + \cdots + \frac{n}{2} \\\\
& = n - 1 \\\\ &  = O(n)
\end{aligned}
$$

之所以能 $O(n)$ 建堆，是因为堆性质很弱，二叉堆并不是唯一的。

要是像排序那样的强条件就难说了。
